package Lagou.Stack;

import java.util.Stack;

/**
 * 例 2：大鱼吃小鱼
 * 【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，
 * Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。
 * 这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:
 * 所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
 * 当方向相对时，大鱼会吃掉小鱼；
 * 鱼的大小都不一样。
 **/
class Stack02 {
    //这道题的关键仍然是如何使用栈来模拟鱼的消除行为
    int solution(int[] fishSize, int[] fishDirection) {
        //鱼的数量
        int fishNumber = fishSize.length;
        if (fishNumber <= 1) return fishNumber;
        //0，1表示鱼游动的方向
        int left = 0;
        int right = 1;

        Stack<Integer> t = new Stack<>();
        for (int i = 0; i < fishNumber; i++) {
            //当前鱼的情况：游动的方向和大小
            int curFishDirection = fishDirection[i];
            int curFishSize = fishSize[i];

            //当前鱼是否被吃掉
            boolean hasEat = false;
            //如果栈中还有鱼，并且栈中鱼向右，当前的鱼向左游，那么就会有相遇的可能性
            while (!t.empty() && fishDirection[t.peek()] == right && curFishDirection == left) {
                //如果栈顶的鱼比较大，那么把新来的吃掉
                if (fishSize[t.peek()] > curFishSize) {
                    hasEat = true;
                    break;
                }
                //如果栈中的鱼较小，那么会把栈中的鱼吃掉，栈中的鱼被消除，所以需要弹栈。
                t.pop();
            }
            //如果新来的鱼，没有被吃掉，那么压入栈中。
            if (!hasEat) {
                t.push(i);
            }
        }

    return t.size();
    }
}
